Networks are a principal means of exchanging or transferring information, such as information signals representing voice, audio, data or video, among communication devices. Such communication devices often include devices for sending and/or receiving information, such as computer terminals, multimedia workstations, facsimile machines, printers, servers and telephones. Information transmitted on the network can be of many different forms but is often formatted into fixed-length data packets or cells. Networks, such as broadband ISDN (BISDN) employing asynchronous transfer mode (ATM) packet switching, are increasingly being used for the reliable, high-speed transmission of information. This increased use has brought major changes in network architecture and infrastructure design, as well as in network operations, to increase communication capacity and quality.
A typical network includes switch nodes having ports coupled by links to ports of other nodes and to the communication devices. Each link is uni- or bi-directional and is characterized by a bandwidth or link capacity in the directions of information transfer. Information to be exchanged is often conveyed over a path containing a set of nodes and links connecting two devices. Such a path can be regarded as a "virtual circuit" (VC) whereby one communication device specifies the intended destination device for the information, and the network delivers the information as though a dedicated circuit connected the two communication devices. Often multiple VCs are simultaneously maintained through a single switch node. In a similar manner, different VCs are often simultaneously maintained over a common link between switch nodes.
Buffer memories are typically employed in the switch nodes to increase the number of VC's that can simultaneously be carried by the node by buffering transmission of data packets of a type that is relatively delay insensitive while buffering to a lesser extent transmission of those packets of a type that is relatively delay sensitive. Such buffer memories effectively operate as respective queues for the packets that are to be conveyed through the respective ports to a common link or multiple links. By selecting an advantageous order in which packets from these queues are routed through a common switch node or multiplexed over a common link, it is possible to increase the number of VCs that the switch node can simultaneously maintain as well as increase communication quality.
In particular networks, a template is used to provide the transmission scheduling order for data packets of the respective VCs. A conventional template includes a fixed number of slots, wherein each slot position represents a scheduling position of corresponding packets for a particular VC. The order of such slots in the template determines the order or sequence in which the switch node repetitively transmits packets for the corresponding VCs. Desirable scheduling orders that facilitate increased VC capacity and improved quality of service transmit packets for VCs of relatively delay sensitive information in a manner that is substantially regular such as, for example, at least roughly periodic and non-bursty.
Known methods for determining scheduling orders or template slot positions include round robin and golden ratio techniques which are described in Y. Arian and Y. Levy, "Algorithms for Generalized Round Robin Routing", Operations Research Letters, vol. 12, no. 5, pp. 313-319 (November 1992), and A. Itai and Z. Rosberg, "A Golden Ratio Control Policy for a Multiple-Access Channel", IEEE Trans. on Automatic Control, vol. AC-29, no. 8, pp. 712-718 (August 1984), respectively, and which are both incorporated by reference herein. However, such scheduling methods provide marginally enhanced ordering of the template slots and, at times, overlook more advantageous slot orderings.
Accordingly, a need exists for a technique for determining improved scheduling templates orderings.